/*
实验2-7 稀疏矩阵的链式结构构建
分数 25
作者 陈越
单位 浙江大学

请设计两个函数，一个根据读入的“行号 列号
元素值”三元组构建十字链表表示的稀疏矩阵，另一个从矩阵中查询指定行列上元素的值。
函数接口定义：

SparseMatrix BuildSparseMatrix( int n_row, int n_col, int n );
ElemSet GetElem( SparseMatrix matrix, int row, int col );

其中稀疏矩阵 SparseMatrix 的十字链表结构定义如下：
typedef enum { head, term } NodeTag;
struct TermNode { /* 非零元素结点
    int row, col; /* 行号，列号
    ElemSet value;/* 元素值
};

typedef struct SparseMatrixNode *Position; /* 结点位置是指针
typedef Position SparseMatrix;
struct SparseMatrixNode {
    Position down;            /* 向下的列指针
    Position right;           /* 向右的行指针
    NodeTag tag;              /* 结点标记
    union {
        Position next;        /* 头结点链接指针
        struct TermNode term; /* 非零元素结点
    } u_region;               /* head和term的共用体
};

函数接口定义中，ElemSet 是用户定义的数据类型，这里默认为 int。函数
BuildSparseMatrix 的功能是创建 n_row 行、n_col 列、有 n
个非零元素的矩阵，非零元素按行优先、列号增序输入。注意：行、列号从 0 开始。函数
GetElem 的功能是返回矩阵 matrix 中第 row 行、第 col
列的元素值。若输入的行、列号非法，则在一行中输出 ERROR 并返回 0。

输入样例：

4 5 7
0 0 18
0 3 2
1 1 27
2 3 -4
3 0 23
3 1 -1
3 4 12
6
0 0
3 4
1 1
2 3
1 4
2 2

输出样例：

18
12
27
-4
0
0
*/

#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet;
typedef enum { head, term } NodeTag;
struct TermNode {  /* 非零元素结点 */
    int row, col;  /* 行号，列号 */
    ElemSet value; /* 元素值 */
};
typedef struct SparseMatrixNode *Position; /* 结点位置是指针 */
typedef Position SparseMatrix;
struct SparseMatrixNode {
    Position down;  /* 向下的列指针 */
    Position right; /* 向右的行指针 */
    NodeTag tag;    /* 结点标记 */
    union {
        Position next;        /* 头结点链接指针 */
        struct TermNode term; /* 非零元素结点 */
    } u_region;               /* head和term的共用体 */
};

SparseMatrix BuildSparseMatrix(int n_row, int n_col, int n);
ElemSet GetElem(SparseMatrix matrix, int row, int col);

int main(void) {
    SparseMatrix matrix;
    int n_row, n_col, n;
    int m, row, col, i;

    scanf("%d %d %d", &n_row, &n_col, &n);
    matrix = BuildSparseMatrix(n_row, n_col, n);
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d %d", &row, &col);
        printf("%d\n", GetElem(matrix, row, col));
    }

    return 0;
}
/* 你的代码将被嵌在这里 */

SparseMatrix BuildSparseMatrix(int n_row, int n_col, int n) {
    SparseMatrix matrix;
    Position p, q;
    int i, row, col;
    ElemSet value;

    // 创建矩阵头节点
    matrix = (Position)malloc(sizeof(struct SparseMatrixNode));
    matrix->tag = head;
    matrix->down = matrix->right = NULL;

    // 创建行头节点数组
    Position *row_heads = (Position *)malloc(n_row * sizeof(Position));
    for (i = n_row - 1; i >= 0; i--) {
        row_heads[i] = (Position)malloc(sizeof(struct SparseMatrixNode));
        row_heads[i]->tag = head;
        row_heads[i]->right = NULL;
        row_heads[i]->down = i == n_row - 1 ? NULL : row_heads[i + 1];
        matrix->u_region.next = row_heads[i];
    }
    matrix->down = row_heads[0];

    // 创建列头节点数组
    Position *col_heads = (Position *)malloc(n_col * sizeof(Position));
    for (i = n_col - 1; i >= 0; i--) {
        col_heads[i] = (Position)malloc(sizeof(struct SparseMatrixNode));
        col_heads[i]->tag = head;
        col_heads[i]->right = i == n_col - 1 ? NULL : col_heads[i + 1];
        col_heads[i]->down = NULL;
        matrix->u_region.next = col_heads[i];
    }
    matrix->right = col_heads[0];

    // 输入非零元素并插入十字链表
    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &row, &col, &value);

        p = (Position)malloc(sizeof(struct SparseMatrixNode));
        p->tag = term;
        p->u_region.term.row = row;
        p->u_region.term.col = col;
        p->u_region.term.value = value;

        // 插入到行链表
        q = row_heads[row];
        while (q->right && q->right->u_region.term.col < col)
            q = q->right;
        p->right = q->right;
        q->right = p;

        // 插入到列链表
        q = col_heads[col];
        while (q->down && q->down->u_region.term.row < row)
            q = q->down;
        p->down = q->down;
        q->down = p;
    }

    free(row_heads);
    free(col_heads);

    return matrix;
}


ElemSet GetElem(SparseMatrix matrix, int row, int col) {
    // 检查行列号是否合法
    if (row < 0 || col < 0) {
        printf("ERROR\n");
        return 0;
    }

    // 找到指定行
    Position row_head = matrix->down;
    for (int i = 0; i < row && row_head; i++) {
        row_head = row_head->down;
    }
    if (row_head == NULL) {
        printf("ERROR\n");
        return 0;
    }
    // 找到指定列
    for (Position p = row_head->right; p != NULL && p->u_region.term.col <= col; p = p->right) {
        if (p->u_region.term.col == col) {
            return p->u_region.term.value;
        }
    }

    // 如果没有找到，返回 0
    return 0;
}